LC 337. House Robber III

Posted on | In |

Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.

1
2
3
4
5
6
7
8
9
Example 1:
Input: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \
     3   1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Solution

Without doubt, we should use recursion to deal with this problem, for every node, we have 2 options, rob it or not.

1
2
3
4
5
6
7
8
class Solution:
    def rob(self, root):
        def dfs(node):
            if not node: return (0, 0)
            l, r = dfs(node.left), dfs(node.right)
            # return (the maximum money if rob this node, the maximum money if don't rob this node)
            return (node.val + l[1] + r[1], max(l[0], l[1]) + max(r[0], r[1]))
        return max(dfs(root))
Donate comment here